#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	unordered_map<int, int> nodeMap;
	vector<int> post;
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
		for (int i = 0; i < inorder.size(); i++)
			nodeMap[inorder[i]] = i;
		post=postorder;
		TreeNode *root = buildTree(0,inorder.size()-1,0,postorder.size()-1);
		return root;
	}

	TreeNode* buildTree(int in_left, int in_right, int post_left, int post_right) {
		if (in_left > in_right || post_left > post_right) return NULL;
		int root = post[post_right];
		int root_pos = nodeMap[root];
		TreeNode* node=new TreeNode(root);
		node->left = buildTree(in_left, root_pos - 1, post_left,post_left + root_pos - in_left - 1);
		node->right = buildTree(root_pos + 1, in_right, post_left + root_pos - in_left, post_right - 1);
		return node;
	}
};

void main() {
	Solution s;
	vector<int> in = { 9,3,15,20,7 };
	vector<int> post = { 9,15,7,20,3 };
	s.buildTree(in, post);
}